//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-
//position-of-element-in-sorted-array/ 
//
// Related Topics 数组 二分查找 👍 434 👎 0


package leetcode.editor.cn;
class 在排序数组中查找数字I{
    public static void main(String[] args) {
        Solution solution = new 在排序数组中查找数字I().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int search(int[] nums, int target) {
        return find(nums,0,nums.length - 1,target);
    }
    
    public int find(int[] nums, int left, int right, int target){
        if (left > right) return 0;
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target ){
            return repeat(nums,mid);
        } else if (nums[mid] > target) {
            return find(nums,left,mid - 1,target);
        }else {
            return find(nums,mid + 1,right,target);
        }
    }
    
    public int repeat(int[] nums,int rp){
        int ans = nums[rp], times = 1;
        for (int i = rp + 1; i < nums.length; i++) {
            if (nums[i] != ans) break;
            times++;
        }
        for (int i = rp - 1; i >= 0; i--) {
            if (nums[i] != ans) break;
            times++;
        }
        return times;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}

